package 力扣.贪心;

public class 非递减数列665 {
    public static void main(String[] args) {
//        int[] ints = {4, 2, 3};
//        int[] ints = {1,2,1,1,1,1,1};
//        int[] ints = {1,1,1,1,2,1,1};
//        int[] ints = {1};
//        int[] ints = {3,4,2,3};
//        int[] ints = {2,3,3,2,2};
//        int[] ints = {1,3,5,2,4};
//        int[] ints = {6,7,8,1,2,3};
//        int[] ints = {5,7,1,8};//715   719 751
//        int[] ints = {1,2,5,3,3};
        int[] ints = {-1,4,2,3};


        boolean b = checkPossibility2(ints);
        System.out.println(b);
    }
    public static boolean checkPossibility(int[] nums) {
        int len = nums.length;
        if (len < 3){
            return true;
        }
        int flag = 0;
        //(321 312 322) (132 231 232) (123 213)
        int left = nums[0];
        int mid = nums[1];
        int right = nums[2];
        if (left >= mid && left >= right){//3xx  332
            if (mid > right && left != mid){//321
                return false;
            }else{//312
                if (left == mid){
                    right = mid;
                    flag = 1;
                }
                left = mid;
                flag = 1;
            }
        }
        if (mid >= left && mid > right){//x3x    331
            if (left > right){//231
                right = mid;
                flag = 1;
            }else {//132
                mid = right;
                flag = 1;
            }
        }
        if (right > left && right > mid){//xx3
           if (left > mid){//213  223  213
               mid = left;
               flag = 1;
           }//123不用变
        }
        nums[1] = mid;
        nums[2] = right;
        for (int i = 3; i < nums.length ; i++) {
             if (nums[i] < nums[i-1]){//1,3,5,2,4
                 if (nums[i-1] != nums[i-2] && nums[i-2] <= nums[i]){//135 352
                     nums[i - 1] = nums[i-2];
                     flag++;
                 }else {//2553
                     nums[i] = nums[i-1];
                     flag++;
                 }

             }
        }
        return flag < 2;
    }
    /*
    *
    * */
    public static boolean checkPossibility2(int[] nums) {
        int len = nums.length;
        if (len < 3){//数组长度小于3直接返回true
            return true;
        }
        int flag = 0;//判断更改次数是否超过一次，每次更改都要进行加一
        int left = nums[0];//左边元素
        int mid = nums[1];//中间元素
        if (left > mid){// 前两个元素直接比较 让left一直小于mid即可
            left = mid;
            nums[0] = left;//更变左边元素的值
            flag++;
        }
        for (int i = 2; i < nums.length ; i++) {// nums[i]:右边元素  nums[i-1]:中间元素  nums[i-2]:左边元素
            if (nums[i] < nums[i-1]){// 当 右边元素 < 中间元素 时(即非递增时)， 分两种情况
                 if (nums[i-2] <= nums[i]){//（1）左边元素 <= 右边元素  如：'11111112(中间元素)11111'  和 '125(中间元素)33'
                     nums[i-1] = nums[i];//      改变中间元素
                 }else{
                     nums[i] = nums[i-1];//  （2）左边元素 > 右边元素 如：125(中间元素)19  改变右边元素
                 }
                 //请注意不要更改左边元素，因为它已经确定，贪心策略一旦确定就不能随意改变

                flag++;
            }
            if (flag > 1){
                return false;
            }
        }
        return flag < 2;
    }
}
